<?php
 //演示数组的二分查找算法
 //前提：
 //1.索引数组
 //2.数组已经排好序了

 //原理：每次都找改数组的某一段的中间项，并跟要找的目标进行‘对比’
 //1.如果刚好相等，则算找出来
 //2.如果中间项比目标大，则只要去左边哪一半找
 //3.如果中间项比目标小，则只要去右边那一半找

 //方法1
 function binary_search($arr,$search,$start,$end){
     if($start>$end){
         return false;
     }
     $mid = floor(($start+$end)/2);
     $mid_value = $arr[$mid];
     if($mid_value == $search){
         return true;
     }else if($mid_value>$search){
         $new_start = $start;
         $new_end = $mid-1;
         return binary_search($arr,$search,$new_start,$new_end);
     }else{
         $new_start = $mid+1;
        $new_end = $end;
        return binary_search($arr,$search,$new_start,$new_end);
     }
 }




//方法2

function binary_search2($arr,$search,$start,$end){
    if($start>$end){
        return false;
    }
    for($i=1;$i>0;$i++){
       $mid = floor(($start+$end)/2);
       $mid_value = $arr[$mid];
       if($mid_value == $search){
           return true;
       }else if($mid_value >$search){
           $start = $start;
           $end = $mid-1;
       }else{
           $start = $mid+1;
           $end = $end;
       }
    }
}


$arr= [1,2,3,4,5,6,7,8,9];
$len = count($arr);
$a = microtime();
var_dump( binary_search($arr,9,0,$len-1));
$b = microtime();
var_dump( binary_search2($arr,9,0,$len-1));
$c = microtime();
echo "<br>",$b-$a;
echo "<br>",$c-$b;
?>